package com.suanfa.search;

/**
 * Created by buguniao on 16/2/27.
 */
public class BinarySearch {
    public static void main(String[] args){
        int[] arr=new int[10000000];
        for(int i=0;i<arr.length;i++){
            arr[i]=i;
        }
        long t1=System.currentTimeMillis();
        int x=search(arr,100000001);
        //int x=search(arr,0,arr.length-1,898);
        long t2=System.currentTimeMillis();
        System.out.println(x+","+(t2-t1));
    }
    public static int search(int[] arr,int lo,int hi,int key){
        if(hi<lo){
           return lo;
        }
        int mid = lo+(hi-lo)/2;
        int comp = key-mid;
        if(comp<0){
           return search(arr, lo, mid - 1, key);
        }else if(comp>0){
           return search(arr, mid + 1, hi, key);
        }else{
            return mid;
        }
    }

    public static int search(int[] arr,int key){
        int lo=0,hi=arr.length-1;
        int rs=-1;
        while(lo<=hi){
            int mid=lo+(hi-lo)/2;
            int comp = key-mid;
            if(comp<0){
                hi=mid-1;
            }else if(comp>0){
                lo=mid+1;
            }else{
                return mid;
            }
        }
        return lo;
    }
}
